package com.example.leetcode.slidingwindow.common;

import javafx.util.Pair;

import java.util.*;

public class SlidingWindowUtils {
    public static int minOperations(int[] nums, int x) {
        int iniSum = Arrays.stream(nums).sum();
        if (iniSum < x) {
            return -1;
        } else if (iniSum == x) {
            return nums.length;
        } else {
            int left = -1;
            int right = 0;
            int result = Integer.MAX_VALUE;
            int n = nums.length;
            int preSum = 0;
            int sufSum = iniSum;
            while (true) {
                while (preSum + sufSum > x && right < n) {
                    sufSum = sufSum - nums[right];  // 判断当前窗口对应的题目的解
                    right = right + 1;  // 如果符合题目条件，就一直往窗口添加新元素   窗口的右边界右移-添加新元素
                }
                if (preSum + sufSum == x) {
                    result = Math.min(result, left + 1 + n - right);
                }
                if (preSum >= x) {
                    break;
                }
                // 将窗口的左边界右移 - 删除窗口元素
                left = left + 1;
                preSum = preSum + nums[left];
            }
            return result == Integer.MAX_VALUE ? -1 : result;
        }
    }

    public static int lengthOfLongestSubstringPro(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        int result = 0;
        // 窗口范围为 [left, right] 闭区间
        int left = 0;
        int right = 0;
        Map<String, Integer> map = new HashMap<>();
        while (right < s.length()) {
            String c = String.valueOf(s.charAt(right));
            Integer beforeIndex = map.get(c);
            map.put(c, right);
            if (beforeIndex != null && beforeIndex >= left) {
                result = Math.max(result, right - left);
                left = beforeIndex + 1;
            }
            right++;
        }
        result = Math.max(result, right - left);
        return result;
    }

    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        int result = 0;
        // 窗口范围为 [left, right] 闭区间
        int left = 0;
        int right = 0;
        while (left < s.length()) {
            while (right < s.length()) {
                if (!checkWindow(s, left, right)) {
                    break;
                }
                result = Math.max(result, right - left + 1);
                right++;
            }
            left++;
        }
        return result;
    }

    private static boolean checkWindow(String s, int left, int right) {
        if (left == right) {
            return true;
        }
        if (left == right - 1) {
            return s.charAt(left) != s.charAt(right);
        }
        String sub = s.substring(left, right);
        char c = s.charAt(right);
        for (int i = 0; i < sub.length(); i++) {
            if (sub.charAt(i) == c) {
                return false;
            }
        }
        return true;
    }

    public static int findMaxConsecutiveOnes(int[] nums) {
        int left = 0;
        int right = 0;
        boolean flag = false;
        int result = 0;
        while (right <= nums.length - 1) {
            if (nums[right] == 1) {
                if (!flag) {
                    flag = true;
                    left = right;
                }
            } else {
                if (flag) {
                    result = Math.max(result, right - left);
                    flag = false;
                }
            }
            right++;
        }
        if (flag) {
            result = Math.max(result, right - left);
        }
        return result;
    }

    public static int minSubArrayLen(int target, int[] nums) {
        int result = nums.length + 1;
        int left = 0;
        int right = 0;
        int sum = 0;
        while (right <= nums.length) {
            while (right < nums.length && sum < target) {
                sum += nums[right];
                right++;
            }
            if (sum < target) {
                break;
            }
            result = Math.min(result, right - left);
            sum -= nums[left];
            left++;
            if (left == nums.length) {
                break;
            }
        }
        return result > nums.length ? 0 : result;
    }

    public static int findMaxConsecutiveOnes2(int[] nums) {
        List<Pair<Integer, Integer>> list = new ArrayList<>();
        int left = 0;
        int right = 0;
        while (right < nums.length) {
            if (nums[right] != nums[left]) {
                Pair<Integer, Integer> pair = new Pair<>(nums[left], right - left);
                list.add(pair);
                left = right;
            } else {
                right++;
            }
        }
        // 加入末尾最后一截字符串
        Pair<Integer, Integer> pair = new Pair<>(nums[left], right - left);
        list.add(pair);
        int ans = 0;
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).getKey() == 1) {
                // 默认最长长度是当前1的长度
                ans = Math.max(ans, list.get(i).getValue());
                // 左边有0
                if (i - 1 >= 0) {
                    if (i - 2 >= 0 && list.get(i - 1).getValue() == 1) {
                        // 左边恰好一个0并且0的左边还有1
                        ans = Math.max(ans, list.get(i).getValue() + 1 + list.get(i - 2).getValue());
                    } else {
                        ans = Math.max(ans, list.get(i).getValue() + 1);
                    }
                }
                // 右边有0
                if (i + 1 < list.size()) {
                    if (i + 2 < list.size() && list.get(i + 1).getValue() == 1) {
                        // 右边恰好一个0并且0的右边还有1
                        ans = Math.max(ans, list.get(i).getValue() + 1 + list.get(i + 2).getValue());
                    } else {
                        ans = Math.max(ans, list.get(i).getValue() + 1);
                    }
                }
            } else {
                // 如果当前片段是0
                ans = Math.max(ans, 1);
            }
        }
        return ans;
    }

    public static int findMaxConsecutiveOnes3(int[] nums) {
        int n = nums.length;
        // 窗口的两个边界，以及 cnt 用来记录出现 0 的个数
        int left = 0;
        int right = 0;
        int cnt = 0;
        // 返回值
        int ans = 0;
        while (right < n) {
            // 只要右边界不越界，而且0的个数小于等于 1 个，那么就扩充右边界
            while (right < n && cnt <= 1) {
                if (nums[right] == 0) {
                    cnt++;
                }
                right++;
                // 及时更新返回值
                if (cnt <= 1) {
                    ans = Math.max(right - left, ans);
                }
            }
            // 向右缩小左边界，直到 0 的个数小于等于 1
            while (left <= right && cnt > 1) {
                if (nums[left] == 0) {
                    cnt--;
                }
                left++;
            }
        }
        return ans;
    }

    public static double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        // 窗口初始化
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        double ans = sum * 1.0 / k;
        // 窗口为 [left, right) 左闭右开区间
        int left = 0;
        int right = k;
        // 当前区间还有效
        while (right < nums.length) {
            sum += nums[right];
            sum -= nums[left];
            // 更新结果
            ans = Math.max(ans, sum * 1.0 / k);
            // 窗口左右边界同时右移一
            right++;
            left++;
        }
        return ans;
    }

    /**
     * 至多包含两个不同字符的最长子串
     * <p>
     * 2换为 K 可得340题题解
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstringTwoDistinct(String s) {
        // 窗口区间是左闭右开区间 [left, right)
        int left = 0;
        int right = 0;
        int ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        boolean flag = false;
        while (right < s.length()) {
            while (right < s.length()) {
                if (!flag) {
                    map.merge(s.charAt(right), 1, Integer::sum);
                    // 如果已经加入窗口，则不再重复添加
                    flag = true;
                }
                // 2换为 K 可得340题题解
                if (map.keySet().size() > 2) {
                    // 走break推出循环时会导致新字符已经加入窗口但是没有计算结果，后续移除左侧元素之后无需重复添加字符
                    break;
                }
                ans = Math.max(ans, right - left + 1);
                right++;
                flag = false;
            }
            // 2换为 K 可得340题题解
            while (left <= right && map.keySet().size() > 2) {
                map.merge(s.charAt(left), -1, Integer::sum);
                if (map.get(s.charAt(left)) == 0) {
                    map.remove(s.charAt(left));
                }
                left++;
            }
        }
        return ans;
    }

    /**
     * 340. 至多包含 K 个不同字符的最长子串
     * <p>
     * 至多包含 K 个不同字符的最长子串
     * 此题的题解 只需要将 方法lengthOfLongestSubstringTwoDistinct() 中的2换为 k 即可
     * 此题中的 k 换为 2 即可得  159. 至多包含两个不同字符的最长子串  的答案
     *
     * @param s
     * @param k
     * @return
     */
    public static int lengthOfLongestSubstringKDistinct(String s, int k) {
        // 窗口区间是左闭右开区间 [left, right)
        int left = 0;
        int right = 0;
        int ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        boolean flag = false;
        while (right < s.length()) {
            while (right < s.length()) {
                if (!flag) {
                    map.merge(s.charAt(right), 1, Integer::sum);
                    // 如果已经加入窗口，则不再重复添加
                    flag = true;
                }
                if (map.keySet().size() > k) {
                    // 走break推出循环时会导致新字符已经加入窗口但是没有计算结果，后续移除左侧元素之后无需重复添加字符
                    break;
                }
                ans = Math.max(ans, right - left + 1);
                right++;
                flag = false;
            }
            while (left <= right && map.keySet().size() > k) {
                map.merge(s.charAt(left), -1, Integer::sum);
                if (map.get(s.charAt(left)) == 0) {
                    map.remove(s.charAt(left));
                }
                left++;
            }
        }
        return ans;
    }
}
